package dwa;

/**
 *
 * @author Wichrowski
 */
public class Sort {

    public static interface Comparer {

        public int compare(Object a, Object b);
    }

    public static interface Comparable {

        public int compareTo(Object other);
    }
    private static Comparer comparable_comparer = new Comparer() {
        public int compare(Object a, Object b) {
            return ((Comparable) a).compareTo(b);
        }
    };

    public static void st(Comparable[] a) {
        st(a, 0, a.length - 1, false, comparable_comparer);
    }

    public static void st(Object[] a, Comparer c) {
        st(a, 0, a.length - 1, false, c);
    }

    public static void st(Object[] a, int from, int to, boolean up, Comparer c) {
        if ((a == null) || (a.length < 2)) {
            return;
        }

        int i = from, j = to;
        Object center = a[(from + to) / 2];
        do {
            if (up) {
                while ((i < to) && (c.compare(center, a[i]) > 0)) {
                    i++;
                }
                while ((j > from) && (c.compare(center, a[j]) < 0)) {
                    j--;
                }
            } else {
                while ((i < to) && (c.compare(center, a[i]) < 0)) {
                    i++;
                }
                while ((j > from) && (c.compare(center, a[j]) > 0)) {
                    j--;
                }
            }

            if (i < j) {
                Object tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
            if (i <= j) {
                i++;
                j--;
            };
        } while (i <= j);

        if (from < j) {
            st(a, from, j, up, c); //recursively sort the rest
        }
        if (i < to) {
            st(a, i, to, up, c);
        }
    }
}
